#include "BuildingPlacer.h"

TilePosition BuildingPlacer::getClosestFit(Point<int, 32> point, UnitType uType, double radius, int padding)
{
	int width = uType.tileWidth()*32;
	int height = uType.tileHeight()*32;
	Point<int,1> p1 = point;
	Point<int,1> p2 = p1;
	p2.x+=width;
	Point<int,1> p3 = p1;
	p3.y+=height;
	Point<int,1> p4 = p3;
	p4.x+=width;

	std::vector<VitalZone> zones;
	std::vector<Position> centroidPoly;
	// If the building lands in a vital zone move away from the centroid of the vital zone centroid polygon.
	// made of the centroids of all the coliding polygons.
	// get all vitalZones in the radius
	double x1 = p1.x;
	double y1 = p1.y;
	double x2, y2;
	Position cpoint;
	for(int i = 0; i < vitalZones.size(); i++) {
		cpoint = vitalZones[i].closestPoint(p1);
		x2 = cpoint.x;
		y2 = cpoint.y;
		if((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) < radius*radius)
			zones.insert(zones.end(), vitalZones[i]);
	}
	// put the vitalZone centroids in as points in centroidPoly and determine if we are inside any zones
	bool inZone = false;
	VitalZone cZone;
	for(int i = 0; i < zones.size(); i++) {
		cZone = zones[i];
		if(cZone.containsPoint(p1) || cZone.containsPoint(p2)
			|| cZone.containsPoint(p3) || cZone.containsPoint(p4)) {
				centroidPoly.insert(centroidPoly.end(), cZone.getCentroid());
				inZone = true;
		}
	}
	if(!inZone && Broodwar->canBuildHere(point,uType))
		return point;
	// calculate the slope of movement from the centroid on the centroid polygon to p1
	// and travel along the vector away from the centroid until a legal build zone to really
	// optimize this algorithm a vitalzone should be placed around all places where things
	// cannot be built, and they should contain the optimum number of vertices.

	// calculate centroid
	double cx=0., cy=0.;
    double signedArea = 0.0;
    double x0 = 0.0; // Current vertex X
    double y0 = 0.0; // Current vertex Y
    x1 = 0.0; // Next vertex X
    y1 = 0.0; // Next vertex Y
    double a = 0.0;  // Partial signed area

    // For all polygon except last
    int i=0;
	for (i=0; i<centroidPoly.size()-1; ++i)
    {
        x0 = centroidPoly[i].x;
        y0 = centroidPoly[i].y;
        x1 = centroidPoly[i+1].x;
        y1 = centroidPoly[i+1].y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        cx += (x0 + x1)*a;
        cy += (y0 + y1)*a;
    }

    // Do last vertex
    x0 = centroidPoly[i].x;
    y0 = centroidPoly[i].y;
    x1 = centroidPoly[0].x;
    y1 = centroidPoly[0].y;
    a = x0*y1 - x1*y0;
    signedArea += a;
    cx += (x0 + x1)*a;
    cy += (y0 + y1)*a;

    signedArea *= 0.5;
    cx /= (6.*signedArea);
    cy /= (6.*signedArea);

	// truncate the values to match bwapi positions
	Position centroid((int)cx, (int)cy);
	Point<double> slopeVector = p1 - centroid;
	if(slopeVector.x == 0.)
		slopeVector.x = .0000001;
	double slope = slopeVector.y / slopeVector.x;

	// normalize slopeVector so its magnitude = 32 == tile size. will be truncated
	slopeVector.x = 8./sqrt(slope*slope + 1.);
	slopeVector.y = slope * slopeVector.x;

	// starting from p1+slopeVecotor and ending when the magnitde of the modification > radius
	// determining if we passed lastX  so base condition off of direction may be < || >
	int lastX = (int)sqrt(radius/(slope*slope + 1.));
	int dir = (p1.x - lastX > 0)? 1:-1;
	do {
		p1 += slopeVector;
		p2 += slopeVector;
		p3 += slopeVector;
		p4 += slopeVector;

		// make sure we can build in the new spot
		for(int i = 0; i < zones.size(); i++) {
			cZone = zones[i];
			if(!cZone.containsPoint(p1) && !cZone.containsPoint(p2)
				&& !cZone.containsPoint(p3) && !cZone.containsPoint(p4)) {
					// not in a vital zone
					if(Broodwar->canBuildHere((TilePosition)p1,uType))
						return (TilePosition)p1;
			}
		}
	} while(((p1.x - lastX > 0)? 1:-1) == dir);
	// no buildable zone was found with this algorithm
	return TilePosition(-1,-1); // end user should check validity of position to determine if it worked
}

VitalZone* BuildingPlacer::addVitalZone(VitalZone& zone, Color color)
{
	Broodwar->printf("adding vital zone.");
	vitalZones.insert(vitalZones.end(),zone);
	return &vitalZones.back();
}
